SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Communication complexity</title>

</head>

Communication complexity

</h1>

</header>

In <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>, communication complexity studies the amount of communication required to solve a problem when the input to the problem is <a href="Distributed_computation" class="mw-redirect" title="Distributed computation">distributed</a> among two or more parties. The study of communication complexity was first introduced by <a href="Andrew_Yao" title="Andrew Yao">Andrew Yao</a> in 1979, while studying the problem of computation distributed among several machines.<a href="#cite_note-yao1979-1">[1]</a>

The problem is usually stated as follows: two parties (traditionally called <a href="Alice_and_Bob" title="Alice and Bob">Alice and Bob</a>) each receive a (potentially different) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-<a href="Bit" title="Bit">bit</a> string <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">. The goal is for Alice to compute the value of a certain function, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)}</annotation>

</semantics>

</math><img src="./29473ed0c4e838ac9dbe074535e507166c0e9101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.607ex; height:2.843ex;" alt="{\displaystyle f(x,y)}" loading="lazy">, that depends on both <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">, with the least amount of <a href="Communication" title="Communication">communication</a> between them.

While Alice and Bob can always succeed by having Bob send his whole <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-bit string to Alice (who then computes the <a href="Function_(mathematics)" title="Function (mathematics)">function</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">), the idea here is to find clever ways of calculating <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> with fewer than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> bits of communication. Note that, unlike in <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, communication complexity is not concerned with the <a href="Computational_complexity" title="Computational complexity">amount of computation</a> performed by Alice or Bob, or the size of the <a href="Computer_memory" title="Computer memory">memory</a> used, as we generally assume nothing about the computational power of either Alice or Bob.

This abstract problem with two parties (called two-party communication complexity), and its general form with <a href="Multiparty_communication_complexity" title="Multiparty communication complexity">more than two parties</a>, is relevant in many contexts. In <a href="VLSI" class="mw-redirect" title="VLSI">VLSI</a> circuit design, for example, one seeks to minimize energy used by decreasing the amount of electric signals passed between the different components during a distributed computation. The problem is also relevant in the study of data structures and in the optimization of computer networks. For surveys of the field, see the textbooks by <a href="#CITEREFRaoYehudayoff2020">Rao & Yehudayoff (2020)</a> and <a href="#CITEREFKushilevitzNisan2006">Kushilevitz & Nisan (2006)</a>.

<div class="mw-heading mw-heading2"><h2 id="Formal_definition">Formal definition</h2></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:X\times Y\rightarrow Z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:X\times Y\rightarrow Z}</annotation>

</semantics>

</math><img src="./0bb07981e04e7bfa76b0ccbd34400002e12a429e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.104ex; height:2.509ex;" alt="{\displaystyle f:X\times Y\rightarrow Z}" loading="lazy"> where we assume in the typical case that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X=Y=\{0,1\}^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X=Y=\{0,1\}^{n}}</annotation>

</semantics>

</math><img src="./4296f7f19168d97f188147be2a3c1d01fb85f4f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.852ex; height:2.843ex;" alt="{\displaystyle X=Y=\{0,1\}^{n}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z=\{0,1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z=\{0,1\}}</annotation>

</semantics>

</math><img src="./2d8c1c3145420944ea12964a899c777236c614a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.463ex; height:2.843ex;" alt="{\displaystyle Z=\{0,1\}}" loading="lazy">. Alice holds an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-bit string <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation>

</semantics>

</math><img src="./3e580967f68f36743e894aa7944f032dda6ea01d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}" loading="lazy"> while Bob holds an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-bit string <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in Y}</annotation>

</semantics>

</math><img src="./cee1c0ec36a82f33f5e3d7434d5667881b4ec323.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.769ex; height:2.509ex;" alt="{\displaystyle y\in Y}" loading="lazy">. By communicating to each other one <a href="Bit" title="Bit">bit</a> at a time (adopting some <a href="Protocol_(computing)" class="mw-redirect" title="Protocol (computing)">communication protocol</a> which is agreed upon in advance), Alice and Bob wish to compute the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)}</annotation>

</semantics>

</math><img src="./29473ed0c4e838ac9dbe074535e507166c0e9101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.607ex; height:2.843ex;" alt="{\displaystyle f(x,y)}" loading="lazy"> such that at least one party knows the value at the end of the communication. At this point the answer can be communicated back so that at the cost of one extra bit, both parties will know the answer. The worst case communication complexity of this communication problem of computing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">, denoted as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D(f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(f)}</annotation>

</semantics>

</math><img src="./9d5afbbd0e5cc5450dff4f0de2006936c4bc3acc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle D(f)}" loading="lazy">, is then defined to be

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(f)=}</annotation>

</semantics>

</math><img src="./9f3f9d34b452eb3f7e248151ab92eecc1249ec65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.465ex; height:2.843ex;" alt="{\displaystyle D(f)=}" loading="lazy"> minimum number of bits exchanged between Alice and Bob in the worst case.</dd></dl>

As observed above, for any function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}</annotation>

</semantics>

</math><img src="./a663c73ab7b3c3afbcd9627719c234f8a43c0403.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.158ex; height:2.843ex;" alt="{\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}" loading="lazy">, we have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D(f)\leq n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(f)\leq n}</annotation>

</semantics>

</math><img src="./393c778ac5405f30ae4e394bdc73f0815d6efbb1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.505ex; height:2.843ex;" alt="{\displaystyle D(f)\leq n}" loading="lazy">.

Using the above definition, it is useful to think of the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> as a <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrix</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> (called the input matrix or communication matrix) where the rows are indexed by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation>

</semantics>

</math><img src="./3e580967f68f36743e894aa7944f032dda6ea01d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}" loading="lazy"> and columns by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in Y}</annotation>

</semantics>

</math><img src="./cee1c0ec36a82f33f5e3d7434d5667881b4ec323.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.769ex; height:2.509ex;" alt="{\displaystyle y\in Y}" loading="lazy">. The entries of the matrix are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{x,y}=f(x,y)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{x,y}=f(x,y)}</annotation>

</semantics>

</math><img src="./f83130b001ab7d34152afd068f2283e56dafad7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.895ex; height:3.009ex;" alt="{\displaystyle A_{x,y}=f(x,y)}" loading="lazy">. Initially both Alice and Bob have a copy of the entire matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> (assuming the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is known to both parties). Then, the problem of computing the function value can be rephrased as "zeroing-in" on the corresponding matrix entry. This problem can be solved if either Alice or Bob knows both <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">. At the start of communication, the number of choices for the value of the function on the inputs is the size of matrix, i.e. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{2n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{2n}}</annotation>

</semantics>

</math><img src="./85543d7c2b7e0fea744a50af20d0f58b0f0fcfb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.203ex; height:2.676ex;" alt="{\displaystyle 2^{2n}}" loading="lazy">. Then, as and when each party communicates a bit to the other, the number of choices for the answer reduces as this eliminates a set of rows/columns resulting in a <a href="Submatrix" class="mw-redirect" title="Submatrix">submatrix</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">.

More formally, a set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\subseteq X\times Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\subseteq X\times Y}</annotation>

</semantics>

</math><img src="./6359bb38c371b192e5c531ca4a75485091c4cf15.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.456ex; height:2.343ex;" alt="{\displaystyle R\subseteq X\times Y}" loading="lazy"> is called a (combinatorial) rectangle if whenever <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1},y_{1})\in R}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1},y_{1})\in R}</annotation>

</semantics>

</math><img src="./e5fa170c1b581e6b21b760f8cca5816db9899e3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.025ex; height:2.843ex;" alt="{\displaystyle (x_{1},y_{1})\in R}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{2},y_{2})\in R}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{2},y_{2})\in R}</annotation>

</semantics>

</math><img src="./8798e0029dccf8d8e4848a40aa305da849da6a2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.025ex; height:2.843ex;" alt="{\displaystyle (x_{2},y_{2})\in R}" loading="lazy"> then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1},y_{2})\in R}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1},y_{2})\in R}</annotation>

</semantics>

</math><img src="./0eba43f365de1b753be268d8d785808fce162643.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.025ex; height:2.843ex;" alt="{\displaystyle (x_{1},y_{2})\in R}" loading="lazy">. Equivalently, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> is a combinatorial rectangle if it can be expressed as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R=M\times N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R=M\times N}</annotation>

</semantics>

</math><img src="./b3a18232f4f2d28011cfc7cff8539b4c76926f5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.209ex; height:2.176ex;" alt="{\displaystyle R=M\times N}" loading="lazy"> for some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M\subseteq X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M\subseteq X}</annotation>

</semantics>

</math><img src="./bf429fb33f3cfe051b0f7ade626d238a65a7473b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.521ex; height:2.343ex;" alt="{\displaystyle M\subseteq X}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\subseteq Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\subseteq Y}</annotation>

</semantics>

</math><img src="./5f11391a102edf90a792fd50c970116c5f42bce7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.935ex; height:2.343ex;" alt="{\displaystyle N\subseteq Y}" loading="lazy">. Consider the case when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> bits are already exchanged between the parties. Now, for a particular <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h\in \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./9485ac52e8e94ea47eccc903cdffc774a1f30105.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.952ex; height:3.176ex;" alt="{\displaystyle h\in \{0,1\}^{k}}" loading="lazy">, let us define a matrix

<msub>

</mrow>

</msub>

</mrow>

<mtext>-bits exchanged on input </mtext>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{h}=\{(x,y):{\text{ the }}k{\text{-bits exchanged on input }}(x,y){\text{ is }}h\}}</annotation>

</semantics>

</math><img src="./27c92a89ebf940ca5b6561666ab7ad5987ada344.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:55.488ex; height:2.843ex;" alt="{\displaystyle T_{h}=\{(x,y):{\text{ the }}k{\text{-bits exchanged on input }}(x,y){\text{ is }}h\}}" loading="lazy"></dd></dl>

Then, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{h}\subseteq X\times Y}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{h}\subseteq X\times Y}</annotation>

</semantics>

</math><img src="./2f2d7fc843ad9d5b105e0b351ab4d963a62e4e30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.229ex; height:2.509ex;" alt="{\displaystyle T_{h}\subseteq X\times Y}" loading="lazy">, and it is not hard to show that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{h}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{h}}</annotation>

</semantics>

</math><img src="./6eaacb63fcdf3a344175b45b3bab7910f8fc3e40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.537ex; height:2.509ex;" alt="{\displaystyle T_{h}}" loading="lazy"> is a combinatorial rectangle in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Example:_EQ">Example: EQ</h3></div>

We consider the case where Alice and Bob try to determine whether or not their input strings are equal. Formally, define the Equality function, denoted <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle EQ:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle EQ:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}</annotation>

</semantics>

</math><img src="./7334330abda676a4108073eb7437cff4c09ded51.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.494ex; height:2.843ex;" alt="{\displaystyle EQ:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}" loading="lazy">, by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle EQ(x,y)=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle EQ(x,y)=1}</annotation>

</semantics>

</math><img src="./da079432c80eb2afbe26234d477f0721134af653.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.203ex; height:2.843ex;" alt="{\displaystyle EQ(x,y)=1}" loading="lazy"> if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=y}</annotation>

</semantics>

</math><img src="./409a91214d63eabe46ec10ff3cbba689ab687366.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.584ex; height:2.009ex;" alt="{\displaystyle x=y}" loading="lazy">. As we demonstrate below, any deterministic communication protocol solving <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle EQ}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle EQ}</annotation>

</semantics>

</math><img src="./0613394868c966e28528f067d7fcb9236b2f483e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.614ex; height:2.509ex;" alt="{\displaystyle EQ}" loading="lazy"> requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> bits of communication in the worst case. As a warm-up example, consider the simple case of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,y\in \{0,1\}^{3}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,y\in \{0,1\}^{3}}</annotation>

</semantics>

</math><img src="./ad2ca6acde632ea304e52bb9609c99abf86e9647.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.098ex; height:3.176ex;" alt="{\displaystyle x,y\in \{0,1\}^{3}}" loading="lazy">. The equality function in this case can be represented by the matrix below. The rows represent all the possibilities of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">, the columns those of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">.

<th>EQ

</th>

<th>000

</th>

<th>001

</th>

<th>010

</th>

<th>011

</th>

<th>100

</th>

<th>101

</th>

<th>110

</th>

<th>111

</th></tr>

<tr>

<th>000

</th>

<td>1

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td></tr>

<tr>

<th>001

</th>

<td>0

</td>

<td>1

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td></tr>

<tr>

<th>010

</th>

<td>0

</td>

<td>0

</td>

<td>1

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td></tr>

<tr>

<th>011

</th>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>1

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td></tr>

<tr>

<th>100

</th>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>1

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td></tr>

<tr>

<th>101

</th>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>1

</td>

<td>0

</td>

<td>0

</td></tr>

<tr>

<th>110

</th>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>1

</td>

<td>0

</td></tr>

<tr>

<th>111

</th>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>0

</td>

<td>1

</td></tr>

</tbody></table>

In this table, the function only evaluates to 1 when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> equals <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> (i.e., on the diagonal). It is also fairly easy to see how communicating a single bit divides someone's possibilities in half. When the first bit of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> is 1, consider only half of the columns (where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> can equal 100, 101, 110, or 111).

<div class="mw-heading mw-heading3"><h3 id="Theorem:_D(EQ)_=_n">Theorem: D(EQ) = n</h3></div>

Proof. Assume that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D(EQ)\leq n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(EQ)\leq n-1}</annotation>

</semantics>

</math><img src="./0aede6c5fda41531b0562f751a206da8bbefc8aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.844ex; height:2.843ex;" alt="{\displaystyle D(EQ)\leq n-1}" loading="lazy">. This means that there exists <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\neq x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\neq x'}</annotation>

</semantics>

</math><img src="./2c6cfab4b1bd197bfe3d7b6ff190cd3ae73f0368.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.443ex; height:3.009ex;" alt="{\displaystyle x\neq x'}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,x)}</annotation>

</semantics>

</math><img src="./72f9e25892f6d000349b8bb6578a59567efbdd63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.503ex; height:2.843ex;" alt="{\displaystyle (x,x)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x',x')}">

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x',x')}</annotation>

</semantics>

</math><img src="./dfc3f52aed3ed3ea5dfa85cfb0533241551cbeb2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.872ex; height:3.009ex;" alt="{\displaystyle (x',x')}" loading="lazy"> have the same communication transcript <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy">. Since this transcript defines a rectangle, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,x')}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,x')}</annotation>

</semantics>

</math><img src="./5703ff3162e7e920c36519054e106f8c4bf8cbef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.466ex; height:3.009ex;" alt="{\displaystyle f(x,x')}" loading="lazy"> must also be 1. By definition <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\neq x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\neq x'}</annotation>

</semantics>

</math><img src="./2c6cfab4b1bd197bfe3d7b6ff190cd3ae73f0368.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.443ex; height:3.009ex;" alt="{\displaystyle x\neq x'}" loading="lazy"> and we know that equality is only true for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a,b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a,b)}</annotation>

</semantics>

</math><img src="./d7e5710198f33b00695903460983021e75860e2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.071ex; height:2.843ex;" alt="{\displaystyle (a,b)}" loading="lazy"> when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=b}</annotation>

</semantics>

</math><img src="./1956b03d1314c7071ac1f45ed7b1e29422dcfcc4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a=b}" loading="lazy">. This yields a contradiction.

This technique of proving deterministic communication lower bounds is called the fooling set technique.<a href="#cite_note-:0-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Randomized_communication_complexity">Randomized communication complexity</h2></div>

In the above definition, we are concerned with the number of bits that must be deterministically transmitted between two parties. If both the parties are given access to a random number generator, can they determine the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> with much less information exchanged? Yao, in his seminal paper<a href="#cite_note-yao1979-1">[1]</a>

answers this question by defining randomized communication complexity.

A randomized protocol <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> for a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> has two-sided error.

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pr[R(x,y)=0]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=0}">

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[R(x,y)=0]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=0}</annotation>

</semantics>

</math><img src="./39f5743f91ce78c002e9e86e66c8a3a30a0a5f50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:33.886ex; height:5.176ex;" alt="{\displaystyle \Pr[R(x,y)=0]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=0}" loading="lazy"></dd></dl>

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pr[R(x,y)=1]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=1}">

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[R(x,y)=1]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=1}</annotation>

</semantics>

</math><img src="./b4240e87e04d8248ed6eaaf08470ce1d1ce95826.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:33.886ex; height:5.176ex;" alt="{\displaystyle \Pr[R(x,y)=1]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=1}" loading="lazy"></dd></dl>

A randomized protocol is a deterministic protocol that uses an extra random string in addition to its normal input. There are two models for this: a public string is a random string that is known by both parties beforehand, while a private string is generated by one party and must be communicated to the other party. A theorem presented below shows that any public string protocol can be simulated by a private string protocol that uses O(log n) additional bits compared to the original.

In the probability inequalities above, the outcome of the protocol is understood to depend only on the random string; both strings x and y remain fixed. In other words, if R(x,y) yields g(x,y,r) when using random string r, then g(x,y,r) = f(x,y) for at least 2/3 of all choices for the string r.

The randomized complexity is simply defined as the number of bits exchanged in such a protocol.

Note that it is also possible to define a randomized protocol with one-sided error, and the complexity is defined similarly.

<div class="mw-heading mw-heading3"><h3 id="Example:_EQ_2">Example: EQ</h3></div>

Returning to the previous example of EQ, if certainty is not required, Alice and Bob can check for equality using only ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy">⁠ messages. Consider the following protocol: Assume that Alice and Bob both have access to the same random string <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z\in \{0,1\}^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z\in \{0,1\}^{n}}</annotation>

</semantics>

</math><img src="./fb46c063f5d38bf3b59d6707dbcec5094facdacf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.831ex; height:2.843ex;" alt="{\displaystyle z\in \{0,1\}^{n}}" loading="lazy">. Alice computes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z\cdot x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z\cdot x}</annotation>

</semantics>

</math><img src="./0ef074cbbbbfbd50b4a5da672491b0fdc6d86cb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.097ex; height:1.676ex;" alt="{\displaystyle z\cdot x}" loading="lazy"> and sends this bit (call it b) to Bob. (The <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\cdot )}</annotation>

</semantics>

</math><img src="./a4c2b509ce21093c430b9c0849fa1aef7f0f1d24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.456ex; height:2.843ex;" alt="{\displaystyle (\cdot )}" loading="lazy"> is the <a href="Dot_product" title="Dot product">dot product</a> in <a href="Finite_field#Some_small_finite_fields" title="Finite field">GF(2)</a>.) Then Bob compares b to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z\cdot y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z\cdot y}</annotation>

</semantics>

</math><img src="./0fb8e86afafa54396111bb40ef2ccc2616f80875.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.923ex; height:2.009ex;" alt="{\displaystyle z\cdot y}" loading="lazy">. If they are the same, then Bob accepts, saying x equals y. Otherwise, he rejects.

Clearly, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=y}</annotation>

</semantics>

</math><img src="./409a91214d63eabe46ec10ff3cbba689ab687366.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.584ex; height:2.009ex;" alt="{\displaystyle x=y}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z\cdot x=z\cdot y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z\cdot x=z\cdot y}</annotation>

</semantics>

</math><img src="./a996a819311abf92b2cb9811c582cb70ad67ad41.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.118ex; height:2.009ex;" alt="{\displaystyle z\cdot x=z\cdot y}" loading="lazy">, so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Prob_{z}[Accept]=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Prob_{z}[Accept]=1}</annotation>

</semantics>

</math><img src="./78dbcb0e425212f1f5793af92475e1c3d6099683.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.325ex; height:2.843ex;" alt="{\displaystyle Prob_{z}[Accept]=1}" loading="lazy">. If x does not equal y, it is still possible that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z\cdot x=z\cdot y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z\cdot x=z\cdot y}</annotation>

</semantics>

</math><img src="./a996a819311abf92b2cb9811c582cb70ad67ad41.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.118ex; height:2.009ex;" alt="{\displaystyle z\cdot x=z\cdot y}" loading="lazy">, which would give Bob the wrong answer. How does this happen?

If x and y are not equal, they must differ in some locations:

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</msup>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</msup>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{cases}x=c_{1}c_{2}\ldots p\ldots p'\ldots x_{n}\\y=c_{1}c_{2}\ldots q\ldots q'\ldots y_{n}\\z=z_{1}z_{2}\ldots z_{i}\ldots z_{j}\ldots z_{n}\end{cases}}}</annotation>

</semantics>

</math><img src="./5b4a2eccebeb8077707b4005d02ee12bc5282a4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:27.938ex; height:8.509ex;" alt="{\displaystyle {\begin{cases}x=c_{1}c_{2}\ldots p\ldots p'\ldots x_{n}\\y=c_{1}c_{2}\ldots q\ldots q'\ldots y_{n}\\z=z_{1}z_{2}\ldots z_{i}\ldots z_{j}\ldots z_{n}\end{cases}}}" loading="lazy"></dd></dl>

Where x and y agree, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{i}*x_{i}=z_{i}*c_{i}=z_{i}*y_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{i}*x_{i}=z_{i}*c_{i}=z_{i}*y_{i}}</annotation>

</semantics>

</math><img src="./3a5eb8a4d4050603f697b112848f8cb77aed5ce7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:24.298ex; height:2.009ex;" alt="{\displaystyle z_{i}*x_{i}=z_{i}*c_{i}=z_{i}*y_{i}}" loading="lazy"> so those terms affect the dot products equally. We can safely ignore those terms and look only at where x and y differ. Furthermore, we can swap the bits <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}}</annotation>

</semantics>

</math><img src="./67d30d30b6c2dbe4d6f150d699de040937ecc95f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.939ex; height:2.009ex;" alt="{\displaystyle y_{i}}" loading="lazy"> without changing whether or not the dot products are equal. This means we can swap bits so that x contains only zeros and y contains only ones:

<mrow>

<mtr>

<mtd>

<msup>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

<msup>

</msup>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{cases}x'=00\ldots 0\\y'=11\ldots 1\\z'=z_{1}z_{2}\ldots z_{n'}\end{cases}}}</annotation>

</semantics>

</math><img src="./061bb5409054ded1f0fae3b467bd068cf87892e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:18.29ex; height:8.509ex;" alt="{\displaystyle {\begin{cases}x'=00\ldots 0\\y'=11\ldots 1\\z'=z_{1}z_{2}\ldots z_{n'}\end{cases}}}" loading="lazy"></dd></dl>

Note that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z'\cdot x'=0}">

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z'\cdot x'=0}</annotation>

</semantics>

</math><img src="./1c4547bb303e17dcf0e00716fba1b11d74df0379.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.729ex; height:2.509ex;" alt="{\displaystyle z'\cdot x'=0}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z'\cdot y'=\Sigma _{i}z'_{i}}">

<msup>

</msup>

<msup>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z'\cdot y'=\Sigma _{i}z'_{i}}</annotation>

</semantics>

</math><img src="./5ea3aa66536fdd34aa3f45c2996a0d7e301f07c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.756ex; height:3.176ex;" alt="{\displaystyle z'\cdot y'=\Sigma _{i}z'_{i}}" loading="lazy">. Now, the question becomes: for some random string <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z'}</annotation>

</semantics>

</math><img src="./7c017ef8616d0c836e4b2a88c40931333c38dd19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.775ex; height:2.509ex;" alt="{\displaystyle z'}" loading="lazy">, what is the probability that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma _{i}z'_{i}=0}">

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma _{i}z'_{i}=0}</annotation>

</semantics>

</math><img src="./1fa38b62ccfce6be8f8dc42b1c777036a18f35f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.62ex; height:2.843ex;" alt="{\displaystyle \Sigma _{i}z'_{i}=0}" loading="lazy">? Since each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z'_{i}}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z'_{i}}</annotation>

</semantics>

</math><img src="./f792eaf4bc63b41a8ea0f37d32d945e94a56b9f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.881ex; height:2.843ex;" alt="{\displaystyle z'_{i}}" loading="lazy"> is equally likely to be 0 or 1, this probability is just <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/2}</annotation>

</semantics>

</math><img src="./e308a3a46b7fdce07cc09dcab9e8d8f73e37d935.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 1/2}" loading="lazy">. Thus, when x does not equal y,

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Prob_{z}[Accept]=1/2}</annotation>

</semantics>

</math><img src="./28779b6e5046f8b693569b781296fc8b7aa0d4fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.65ex; height:2.843ex;" alt="{\displaystyle Prob_{z}[Accept]=1/2}" loading="lazy">. The algorithm can be repeated many times to increase its accuracy. This fits the requirements for a randomized communication algorithm.

This shows that if Alice and Bob share a random string of length n, they can send one bit to each other to compute <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle EQ(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle EQ(x,y)}</annotation>

</semantics>

</math><img src="./e47a70582d9aa3fdc04ab203deef7e5804c95d66.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.942ex; height:2.843ex;" alt="{\displaystyle EQ(x,y)}" loading="lazy">. In the next section, it is shown that Alice and Bob can exchange only ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy">⁠ bits that are as good as sharing a random string of length n. Once that is shown, it follows that EQ can be computed in ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy">⁠ messages.

<div class="mw-heading mw-heading3"><h3 id="Example:_GH">Example: GH</h3></div>

For yet another example of randomized communication complexity, we turn to an example known as the <a href="Gap-Hamming_problem" title="Gap-Hamming problem">gap-Hamming problem</a> (abbreviated GH). Formally, Alice and Bob both maintain binary messages, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,y\in \{-1,+1\}^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,y\in \{-1,+1\}^{n}}</annotation>

</semantics>

</math><img src="./e78337c15bcaf645aa5a27b2cd8e57176cc029ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.878ex; height:2.843ex;" alt="{\displaystyle x,y\in \{-1,+1\}^{n}}" loading="lazy"> and would like to determine if the strings are very similar or if they are not very similar. In particular, they would like to find a communication protocol requiring the transmission of as few bits as possible to compute the following partial Boolean function,

<msub>

</mrow>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

<msqrt>

</msqrt>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msqrt>

</msqrt>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{GH}}_{n}(x,y):={\begin{cases}-1&\langle x,y\rangle \leq {\sqrt {n}}\\+1&\langle x,y\rangle \geq {\sqrt {n}}.\end{cases}}}</annotation>

</semantics>

</math><img src="./b0bb4b17a038bc3184b09264b819ce4385b182fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:34.052ex; height:6.176ex;" alt="{\displaystyle {\text{GH}}_{n}(x,y):={\begin{cases}-1&\langle x,y\rangle \leq {\sqrt {n}}\\+1&\langle x,y\rangle \geq {\sqrt {n}}.\end{cases}}}" loading="lazy"></dd></dl>

Clearly, they must communicate all their bits if the protocol is to be deterministic (this is because, if there is a deterministic, strict subset of indices that Alice and Bob relay to one another, then imagine having a pair of strings that on that set disagree in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {n}}-1}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {n}}-1}</annotation>

</semantics>

</math><img src="./dd45e0bd1b3aa5dcca2d06e2cfc7ddd719308e3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.333ex; height:3.009ex;" alt="{\displaystyle {\sqrt {n}}-1}" loading="lazy"> positions. If another disagreement occurs in any position that is not relayed, then this affects the result of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{GH}}_{n}(x,y)}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{GH}}_{n}(x,y)}</annotation>

</semantics>

</math><img src="./e0cec005ac2ba1b6e1bc8d284fd5aa3752af43fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.114ex; height:2.843ex;" alt="{\displaystyle {\text{GH}}_{n}(x,y)}" loading="lazy">, and hence would result in an incorrect procedure.

A natural question one then asks is, if we're permitted to err <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/3}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/3}</annotation>

</semantics>

</math><img src="./be0712022e81c98e8a44604c1ef399697512e0cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 1/3}" loading="lazy"> of the time (over random instances <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,y}</annotation>

</semantics>

</math><img src="./5ea0abffd33a692ded22accc104515a032851dff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.519ex; height:2.009ex;" alt="{\displaystyle x,y}" loading="lazy"> drawn uniformly at random from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{-1,+1\}^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{-1,+1\}^{n}}</annotation>

</semantics>

</math><img src="./0124fc0c5b184cf3db29479467fe0404c4a13bc9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.519ex; height:2.843ex;" alt="{\displaystyle \{-1,+1\}^{n}}" loading="lazy">), then can we get away with a protocol with fewer bits? It turns out that the answer somewhat surprisingly is no, due to a result of Chakrabarti and Regev in 2012: they show that for random instances, any procedure which is correct at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2/3}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2/3}</annotation>

</semantics>

</math><img src="./f73d0fc4f429ca39387dffad817c8147cf73d0ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 2/3}" loading="lazy"> of the time must send <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n)}</annotation>

</semantics>

</math><img src="./6becc31c61ad3420a1e4ee9e39c28baf73bda24d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.882ex; height:2.843ex;" alt="{\displaystyle \Omega (n)}" loading="lazy"> bits worth of communication, which is to say essentially all of them.

<div class="mw-heading mw-heading3"><h3 id="Public_coins_versus_private_coins">Public coins versus private coins</h3></div>

Creating random protocols becomes easier when both parties have access to the same random string, known as a shared string protocol. However, even in cases where the two parties do not share a random string, it is still possible to use private string protocols with only a small communication cost. Any shared string random protocol using any number of random string can be simulated by a private string protocol that uses an extra O(log n) bits.

Intuitively, we can find some set of strings that has enough randomness in it to run the random protocol with only a small increase in error. This set can be shared beforehand, and instead of drawing a random string, Alice and Bob need only agree on which string to choose from the shared set. This set is small enough that the choice can be communicated efficiently. A formal proof follows.

Consider some random protocol P with a maximum error rate of 0.1. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 100n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 100n}</annotation>

</semantics>

</math><img src="./5ef4cb62b44e80bb9945558cf881737c947356f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.882ex; height:2.176ex;" alt="{\displaystyle 100n}" loading="lazy"> strings of length n, numbered <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{1},r_{2},\dots ,r_{100n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{1},r_{2},\dots ,r_{100n}}</annotation>

</semantics>

</math><img src="./8cc325bf0753bb609e5f1202d736f423984a5f8e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.151ex; height:2.009ex;" alt="{\displaystyle r_{1},r_{2},\dots ,r_{100n}}" loading="lazy">. Given such an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy">, define a new protocol <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P'_{R}}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P'_{R}}</annotation>

</semantics>

</math><img src="./c8ac3ebf79e9296278d85a5c8dfe8d52f5fce723.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.972ex; height:2.843ex;" alt="{\displaystyle P'_{R}}" loading="lazy"> which randomly picks some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{i}}</annotation>

</semantics>

</math><img src="./a0b6d651eaf432dbf1f106021c8bb499ae83fd1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.848ex; height:2.009ex;" alt="{\displaystyle r_{i}}" loading="lazy"> and then runs P using <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{i}}</annotation>

</semantics>

</math><img src="./a0b6d651eaf432dbf1f106021c8bb499ae83fd1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.848ex; height:2.009ex;" alt="{\displaystyle r_{i}}" loading="lazy"> as the shared random string. It takes O(log 100n) = O(log n) bits to communicate the choice of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{i}}</annotation>

</semantics>

</math><img src="./a0b6d651eaf432dbf1f106021c8bb499ae83fd1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.848ex; height:2.009ex;" alt="{\displaystyle r_{i}}" loading="lazy">.

Let us define <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(x,y)}</annotation>

</semantics>

</math><img src="./089e91a1824e14cebc8e8d04dc652c61b3008e0a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:6.587ex; height:2.843ex;" alt="{\displaystyle p(x,y)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p'_{R}(x,y)}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p'_{R}(x,y)}</annotation>

</semantics>

</math><img src="./627ad41c312a05aaaf795151aa36ba67a8c15c06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:8.067ex; height:3.009ex;" alt="{\displaystyle p'_{R}(x,y)}" loading="lazy"> to be the probabilities that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P'_{R}}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P'_{R}}</annotation>

</semantics>

</math><img src="./c8ac3ebf79e9296278d85a5c8dfe8d52f5fce723.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.972ex; height:2.843ex;" alt="{\displaystyle P'_{R}}" loading="lazy"> compute the correct value for the input <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,y)}</annotation>

</semantics>

</math><img src="./41cf50e4a314ca8e2c30964baa8d26e5be7a9386.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.328ex; height:2.843ex;" alt="{\displaystyle (x,y)}" loading="lazy">.

For a fixed <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,y)}</annotation>

</semantics>

</math><img src="./41cf50e4a314ca8e2c30964baa8d26e5be7a9386.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.328ex; height:2.843ex;" alt="{\displaystyle (x,y)}" loading="lazy">, we can use <a href="Hoeffding's_inequality" title="Hoeffding's inequality">Hoeffding's inequality</a> to get the following equation:

</mrow>

</munder>

</mrow>

</mrow>

</msubsup>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}}</annotation>

</semantics>

</math><img src="./45f8000f9397f6ab452081c1b118ba696e24e5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:61.424ex; height:4.343ex;" alt="{\displaystyle \Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}}" loading="lazy"></dd></dl>

Thus when we don't have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,y)}</annotation>

</semantics>

</math><img src="./41cf50e4a314ca8e2c30964baa8d26e5be7a9386.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.328ex; height:2.843ex;" alt="{\displaystyle (x,y)}" loading="lazy"> fixed:

</mrow>

</munder>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</munder>

</mrow>

</munder>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr _{R}[\exists (x,y):\ |p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq \sum _{(x,y)}\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]<\sum _{(x,y)}2^{-2n}=1}</annotation>

</semantics>

</math><img src="./8fe4b3f6e899f3718094a415abc5c37bbef639b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:88.776ex; height:6.009ex;" alt="{\displaystyle \Pr _{R}[\exists (x,y):\ |p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq \sum _{(x,y)}\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]<\sum _{(x,y)}2^{-2n}=1}" loading="lazy"></dd></dl>

The last equality above holds because there are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{2n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{2n}}</annotation>

</semantics>

</math><img src="./85543d7c2b7e0fea744a50af20d0f58b0f0fcfb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.203ex; height:2.676ex;" alt="{\displaystyle 2^{2n}}" loading="lazy"> different pairs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,y)}</annotation>

</semantics>

</math><img src="./41cf50e4a314ca8e2c30964baa8d26e5be7a9386.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.328ex; height:2.843ex;" alt="{\displaystyle (x,y)}" loading="lazy">. Since the probability does not equal 1, there is some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{0}}</annotation>

</semantics>

</math><img src="./9b8916196f182fcbaaca54f931176a4a4f5769cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.818ex; height:2.509ex;" alt="{\displaystyle R_{0}}" loading="lazy"> so that for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,y)}</annotation>

</semantics>

</math><img src="./41cf50e4a314ca8e2c30964baa8d26e5be7a9386.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.328ex; height:2.843ex;" alt="{\displaystyle (x,y)}" loading="lazy">:

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |p'_{R_{0}}(x,y)-p(x,y)|<0.1}</annotation>

</semantics>

</math><img src="./b2f5d39f29980cf6c80991a05b9a8c902d0a0afa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:25.511ex; height:3.343ex;" alt="{\displaystyle |p'_{R_{0}}(x,y)-p(x,y)|<0.1}" loading="lazy"></dd></dl>

Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> has at most 0.1 error probability, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P'_{R_{0}}}">

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P'_{R_{0}}}</annotation>

</semantics>

</math><img src="./1363bc1c558743e3a692e8eb06927d67da22bf7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.803ex; height:3.176ex;" alt="{\displaystyle P'_{R_{0}}}" loading="lazy"> can have at most 0.2 error probability.

<div class="mw-heading mw-heading3"><h3 id="Collapse_of_Randomized_Communication_Complexity">Collapse of Randomized Communication Complexity</h3></div>

Let's say we additionally allow Alice and Bob to share some resource, for example a pair of entangled particles. Using that ressource, Alice and Bob can correlate their information and thus try to 'collapse' (or 'trivialize') communication complexity in the following sense.

Definition. A resource <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> is said to be "collapsing" if, using that resource <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy">, only one bit of classical communication is enough for Alice to know the evaluation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)}</annotation>

</semantics>

</math><img src="./29473ed0c4e838ac9dbe074535e507166c0e9101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.607ex; height:2.843ex;" alt="{\displaystyle f(x,y)}" loading="lazy"> in the worst case scenario for any <a href="Boolean_function" title="Boolean function">Boolean function</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">.

The surprising fact of a collapse of communication complexity is that the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> can have arbitrarily large entry size, but still the number of communication bit is constant to a single one.

Some resources are shown to be non-collapsing, such as quantum correlations <a href="#cite_note-3">[3]</a> or more generally almost-quantum correlations,<a href="#cite_note-4">[4]</a> whereas on the contrary some other resources are shown to collapse randomized communication complexity, such as the PR-box,<a href="#cite_note-5">[5]</a> or some noisy PR-boxes satisfying some conditions.<a href="#cite_note-6">[6]</a><a href="#cite_note-7">[7]</a><a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading3"><h3 id="Distributional_Complexity">Distributional Complexity</h3></div>

One approach to studying randomized communication complexity is through distributional complexity.

Given a joint distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"> on the inputs of both players, the corresponding distributional complexity of a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is the minimum cost of a deterministic protocol <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pr[f(x,y)=R(x,y)]\geq 2/3}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[f(x,y)=R(x,y)]\geq 2/3}</annotation>

</semantics>

</math><img src="./a079ec0ea681763e9c426815d6a8ff71b428698e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.172ex; height:2.843ex;" alt="{\displaystyle \Pr[f(x,y)=R(x,y)]\geq 2/3}" loading="lazy">, where the inputs are sampled according to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy">.

Yao's minimax principle<a href="#cite_note-9">[9]</a> (a special case of <a href="John_von_Neumann" title="John von Neumann">von Neumann</a>'s <a href="Minimax_theorem" title="Minimax theorem">minimax theorem</a>) states that the randomized communication complexity of a function equals its maximum distributional complexity, where the maximum is taken over all joint distributions of the inputs (not necessarily product distributions!).

<a href="Yao's_principle" title="Yao's principle">Yao's principle</a> can be used to prove lower bounds on the randomized communication complexity of a function: design the appropriate joint distribution, and prove a lower bound on the distributional complexity. Since distributional complexity concerns deterministic protocols, this could be easier than proving a lower bound on randomized protocols directly.

As an example, let us consider the disjointness function DISJ: each of the inputs is interpreted as a subset of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{1,\dots ,n\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{1,\dots ,n\}}</annotation>

</semantics>

</math><img src="./8b98091026e0b10ee08a7c77e229c649f81b0a05.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.06ex; height:2.843ex;" alt="{\displaystyle \{1,\dots ,n\}}" loading="lazy">, and DISJ(x,y)=1 if the two sets are disjoint. Razborov<a href="#cite_note-10">[10]</a> proved an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n)}</annotation>

</semantics>

</math><img src="./6becc31c61ad3420a1e4ee9e39c28baf73bda24d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.882ex; height:2.843ex;" alt="{\displaystyle \Omega (n)}" loading="lazy"> lower bound on the randomized communication complexity by considering the following distribution: with probability 3/4, sample two random disjoint sets of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n/4}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n/4}</annotation>

</semantics>

</math><img src="./cbe2692d0ea45b20b501c7490ab5f6a43d7dd58d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.72ex; height:2.843ex;" alt="{\displaystyle n/4}" loading="lazy">, and with probability 1/4, sample two random sets of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n/4}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n/4}</annotation>

</semantics>

</math><img src="./cbe2692d0ea45b20b501c7490ab5f6a43d7dd58d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.72ex; height:2.843ex;" alt="{\displaystyle n/4}" loading="lazy"> with a unique intersection.

<div class="mw-heading mw-heading3"><h3 id="Information_Complexity">Information Complexity</h3></div>

A powerful approach to the study of distributional complexity is information complexity. Initiated by Bar-Yossef, Jayram, Kumar and Sivakumar,<a href="#cite_note-11">[11]</a> the approach was codified in work of Barak, Braverman, Chen and Rao<a href="#cite_note-12">[12]</a> and by Braverman and Rao.<a href="#cite_note-13">[13]</a>

The (internal) information complexity of a (possibly randomized) protocol R with respect to a distribution μ is defined as follows. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (X,Y)\sim \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (X,Y)\sim \mu }</annotation>

</semantics>

</math><img src="./cb0cfe897ae57c8f8845c53a89bb4b8fb7ad2d36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.097ex; height:2.843ex;" alt="{\displaystyle (X,Y)\sim \mu }" loading="lazy"> be random inputs sampled according to μ, and let Π be the transcript of R when run on the inputs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X,Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X,Y}</annotation>

</semantics>

</math><img src="./b8705438171d938b7f59cd1bfa5b7d99b6afa5cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.787ex; height:2.509ex;" alt="{\displaystyle X,Y}" loading="lazy">. The information complexity of the protocol is

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {IC} _{\mu }(R)=I(\Pi ;Y|X)+I(\Pi ;X|Y),}</annotation>

</semantics>

</math><img src="./1f3d7bf8196f802df6565945955a58460df5e96d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:34.217ex; height:3.009ex;" alt="{\displaystyle \operatorname {IC} _{\mu }(R)=I(\Pi ;Y|X)+I(\Pi ;X|Y),}" loading="lazy"></dd></dl>

where I denotes <a href="Information_theory#Mutual_information_(transinformation)" title="Information theory">conditional mutual information</a>.

The first summand measures the amount of information that Alice learns about Bob's input from the transcript, and the second measures the amount of information that Bob learns about Alice's input.

The ε-error information complexity of a function f with respect to a distribution μ is the infimal information complexity of a protocol for f whose error (with respect to μ) is at most ε.

Braverman and Rao proved that information equals amortized communication. This means that the cost for solving n independent copies of f is roughly n times the information complexity of f. This is analogous to the well-known interpretation of <a href="Entropy_(information_theory)" title="Entropy (information theory)">Shannon entropy</a> as the amortized bit-length required to transmit data from a given information source. Braverman and Rao's proof uses a technique known as "protocol compression", in which an information-efficient protocol is "compressed" into a communication-efficient protocol.

The techniques of information complexity enable the computation of the exact (up to first order) communication complexity of set disjointness to be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1.4923\ldots n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1.4923\ldots n}</annotation>

</semantics>

</math><img src="./834aa60e53581815b5b87b2199378964d43c5dae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.351ex; height:2.176ex;" alt="{\displaystyle 1.4923\ldots n}" loading="lazy">.<a href="#cite_note-14">[14]</a>

Information complexity techniques have also been used to analyze extended formulations, proving an essentially optimal lower bound on the complexity of algorithms based on <a href="Linear_programming" title="Linear programming">linear programming</a> which approximately solve the <a href="Clique_problem" title="Clique problem">maximum clique problem</a>.<a href="#cite_note-15">[15]</a>

Omri Weinstein's 2015 survey<a href="#cite_note-16">[16]</a> surveys the subject.

<div class="mw-heading mw-heading2"><h2 id="Quantum_communication_complexity">Quantum communication complexity</h2></div>

Quantum communication complexity tries to quantify the communication reduction possible by using quantum effects during a distributed computation.

At least three quantum generalizations of communication complexity have been proposed; for a survey see the suggested text by G. Brassard.

The first one is the <a href="Quantum_entanglement" title="Quantum entanglement">qubit-communication model</a>, where the parties can use quantum communication instead of classical communication, for example by exchanging <a href="Photons" class="mw-redirect" title="Photons">photons</a> through an <a href="Optical_fiber" title="Optical fiber">optical fiber</a>.

In a second model the communication is still performed with classical bits, but the parties are allowed to manipulate an unlimited supply of quantum entangled states as part of their protocols. By doing measurements on their entangled states, the parties can save on classical communication during a distributed computation (see an application in <a href="#Collapse_of_Randomized_Communication_Complexity">Collapse of Randomized Communication Complexity</a>).

The third model involves access to previously shared entanglement in addition to <a href="Qubit" title="Qubit">qubit</a> communication, and is the least explored of the three quantum models.

<div class="mw-heading mw-heading2"><h2 id="Nondeterministic_communication_complexity">Nondeterministic communication complexity</h2></div>

In nondeterministic communication complexity, Alice and Bob have access to an oracle. After receiving the oracle's word, the parties communicate to deduce <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)}</annotation>

</semantics>

</math><img src="./29473ed0c4e838ac9dbe074535e507166c0e9101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.607ex; height:2.843ex;" alt="{\displaystyle f(x,y)}" loading="lazy">. The nondeterministic communication complexity is then the maximum over all pairs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,y)}</annotation>

</semantics>

</math><img src="./41cf50e4a314ca8e2c30964baa8d26e5be7a9386.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.328ex; height:2.843ex;" alt="{\displaystyle (x,y)}" loading="lazy"> over the sum of number of bits exchanged and the coding length of the oracle word.

Viewed differently, this amounts to covering all 1-entries of the 0/1-matrix by combinatorial 1-rectangles (i.e., non-contiguous, non-convex submatrices, whose entries are all one (see Kushilevitz and Nisan or Dietzfelbinger et al.)). The nondeterministic communication complexity is the <a href="Binary_logarithm" title="Binary logarithm">binary logarithm</a> of the rectangle covering number of the matrix: the minimum number of combinatorial 1-rectangles required to cover all 1-entries of the matrix, without covering any 0-entries.

Nondeterministic communication complexity occurs as a means to obtaining lower bounds for deterministic communication complexity (see Dietzfelbinger et al.), but also in the theory of nonnegative matrices, where it gives a lower bound on the <a href="Nonnegative_rank_(linear_algebra)" title="Nonnegative rank (linear algebra)">nonnegative rank</a> of a nonnegative matrix.<a href="#cite_note-17">[17]</a>

<div class="mw-heading mw-heading2"><h2 id="Unbounded-error_communication_complexity">Unbounded-error communication complexity</h2></div>

In the unbounded-error setting, Alice and Bob have access to a private coin and their own inputs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,y)}</annotation>

</semantics>

</math><img src="./41cf50e4a314ca8e2c30964baa8d26e5be7a9386.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.328ex; height:2.843ex;" alt="{\displaystyle (x,y)}" loading="lazy">. In this setting, Alice succeeds if she responds with the correct value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)}</annotation>

</semantics>

</math><img src="./29473ed0c4e838ac9dbe074535e507166c0e9101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.607ex; height:2.843ex;" alt="{\displaystyle f(x,y)}" loading="lazy"> with probability strictly greater than 1/2. In other words, if Alice's responses have any non-zero correlation to the true value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)}</annotation>

</semantics>

</math><img src="./29473ed0c4e838ac9dbe074535e507166c0e9101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.607ex; height:2.843ex;" alt="{\displaystyle f(x,y)}" loading="lazy">, then the protocol is considered valid.

Note that the requirement that the coin is private is essential. In particular, if the number of public bits shared between Alice and Bob are not counted against the communication complexity, it is easy to argue that computing any function has <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> communication complexity.<a href="#cite_note-18">[18]</a> On the other hand, both models are equivalent if the number of public bits used by Alice and Bob is counted against the protocol's total communication.<a href="#cite_note-19">[19]</a>

Though subtle, lower bounds on this model are extremely strong. More specifically, it is clear that any bound on problems of this class immediately imply equivalent bounds on problems in the deterministic model and the private and public coin models, but such bounds also hold immediately for nondeterministic communication models and quantum communication models.<a href="#cite_note-20">[20]</a>

Forster<a href="#cite_note-21">[21]</a> was the first to prove explicit lower bounds for this class, showing that computing the inner product <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle x,y\rangle }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle x,y\rangle }</annotation>

</semantics>

</math><img src="./9df1806ebe1fed1a728b18aed82c30be8b2a0acb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.328ex; height:2.843ex;" alt="{\displaystyle \langle x,y\rangle }" loading="lazy"> requires at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n)}</annotation>

</semantics>

</math><img src="./6becc31c61ad3420a1e4ee9e39c28baf73bda24d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.882ex; height:2.843ex;" alt="{\displaystyle \Omega (n)}" loading="lazy"> bits of communication, though an earlier result of Alon, Frankl, and Rödl proved that the communication complexity for almost all Boolean functions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\to \{0,1\}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\to \{0,1\}}</annotation>

</semantics>

</math><img src="./b77fb847fc56ef2dfbfec480df93acb18860f1aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.158ex; height:2.843ex;" alt="{\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\to \{0,1\}}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n)}</annotation>

</semantics>

</math><img src="./6becc31c61ad3420a1e4ee9e39c28baf73bda24d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.882ex; height:2.843ex;" alt="{\displaystyle \Omega (n)}" loading="lazy">.<a href="#cite_note-22">[22]</a>

<div class="mw-heading mw-heading2"><h2 id="Lifting">Lifting</h2></div>

Lifting is a general technique in <a href="Computational_complexity_theory" title="Computational complexity theory">complexity theory</a> in which a lower bound on a simple measure of complexity is "lifted" to a lower bound on a more difficult measure.

This technique was pioneered in the context of communication complexity by Raz and McKenzie,<a href="#cite_note-23">[23]</a> who proved the first query-to-communication lifting theorem, and used the result to separate the <a href="Circuit_complexity#Monotone_circuits" title="Circuit complexity">monotone</a> <a href="NC_(complexity)" title="NC (complexity)">NC</a> hierarchy.

Given a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}</annotation>

</semantics>

</math><img src="./45f03afcbbd1be0a0fff8fb2a502a61d1642cd94.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.513ex; height:2.843ex;" alt="{\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}" loading="lazy"> and a gadget <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g\colon \{0,1\}^{a}\times \{0,1\}^{b}\to \{0,1\}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g\colon \{0,1\}^{a}\times \{0,1\}^{b}\to \{0,1\}}</annotation>

</semantics>

</math><img src="./c9ce3db302a814e072f17a138d07c01ead280f27.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.695ex; height:3.176ex;" alt="{\displaystyle g\colon \{0,1\}^{a}\times \{0,1\}^{b}\to \{0,1\}}" loading="lazy">, their composition <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\circ g\colon \{0,1\}^{na}\times \{0,1\}^{nb}\to \{0,1\}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\circ g\colon \{0,1\}^{na}\times \{0,1\}^{nb}\to \{0,1\}}</annotation>

</semantics>

</math><img src="./974ca718ef46588398ef92f1bc12f8ad6685295a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.141ex; height:3.176ex;" alt="{\displaystyle f\circ g\colon \{0,1\}^{na}\times \{0,1\}^{nb}\to \{0,1\}}" loading="lazy"> is defined as follows:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (f\circ g)(x,y)=f(g(x_{1,1}\cdots x_{1,a},y_{1,1}\cdots y_{1,b}),\dots ,g(x_{n,1}\cdots x_{n,a},y_{n,1}\cdots y_{n,b})).}</annotation>

</semantics>

</math><img src="./442551968b3d327931380da57f94575af1ca49a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:74.71ex; height:3.009ex;" alt="{\displaystyle (f\circ g)(x,y)=f(g(x_{1,1}\cdots x_{1,a},y_{1,1}\cdots y_{1,b}),\dots ,g(x_{n,1}\cdots x_{n,a},y_{n,1}\cdots y_{n,b})).}" loading="lazy"></dd></dl>

In words, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is partitioned into <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> blocks of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> is partitioned into <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> blocks of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy">. The gadget is applied <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> times on the blocks, and the outputs are fed into <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">. Diagrammatically:

In this diagram, each of the inputs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}</annotation>

</semantics>

</math><img src="./d3c14f9a48493fddce4d25d3265914b2301cccc9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.273ex; height:2.009ex;" alt="{\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}" loading="lazy"> is a bits long, and each of the inputs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{n}}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{n}}</annotation>

</semantics>

</math><img src="./478f493cc7a5b9808a943b2e480b937a60a2df95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.273ex; height:2.176ex;" alt="{\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{n}}" loading="lazy"> is b bits long.

A <a href="Decision_tree_model" title="Decision tree model">decision tree</a> of depth <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta }</annotation>

</semantics>

</math><img src="./32769037c408874e1890f77554c65f39c523ebe2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.936ex; height:2.176ex;" alt="{\displaystyle \Delta }" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> can be translated to a communication protocol whose cost is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta \cdot D(g)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta \cdot D(g)}</annotation>

</semantics>

</math><img src="./bd9c6d4103a753accb6d7b47656bd75b84e5e80b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.465ex; height:2.843ex;" alt="{\displaystyle \Delta \cdot D(g)}" loading="lazy">: each time the tree queries a bit, the corresponding value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> is computed using an optimal protocol for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy">. Raz and McKenzie showed that this is optimal up to a constant factor when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> is the so-called "indexing gadget", in which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> has length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\log n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\log n}</annotation>

</semantics>

</math><img src="./e02718bc6bf005fe0710fd8290d4cfbbbc76f5c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.148ex; height:2.509ex;" alt="{\displaystyle c\log n}" loading="lazy"> (for a large enough constant c), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> has length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{c}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{c}}</annotation>

</semantics>

</math><img src="./3a62b39da47c098d4cec1ac794318335b381c436.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.339ex; height:2.343ex;" alt="{\displaystyle n^{c}}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x,y)}</annotation>

</semantics>

</math><img src="./bf358a54b0375e22ae5f3ab2c3e1a22c0c87e11c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.444ex; height:2.843ex;" alt="{\displaystyle g(x,y)}" loading="lazy"> is the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">-th bit of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">.

The proof of the Raz–McKenzie lifting theorem uses the method of simulation, in which a protocol for the composed function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\circ g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\circ g}</annotation>

</semantics>

</math><img src="./b2f61ca7838709fbae07dce9c0d513770f10cfae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.589ex; height:2.509ex;" alt="{\displaystyle f\circ g}" loading="lazy"> is used to generate a decision tree for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">. Göös, Pitassi and Watson<a href="#cite_note-24">[24]</a> gave an exposition of the original proof. Since then, several works have proved similar theorems with different gadgets, such as inner product.<a href="#cite_note-25">[25]</a> The smallest gadget which can be handled is the indexing gadget with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c=1+\epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=1+\epsilon }</annotation>

</semantics>

</math><img src="./d8b8ab1c8a4c026cf4ff9159968b946c5c86e4af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.052ex; height:2.343ex;" alt="{\displaystyle c=1+\epsilon }" loading="lazy">.<a href="#cite_note-26">[26]</a>

Göös, Pitassi and Watson extended the Raz–McKenzie technique to randomized protocols.<a href="#cite_note-27">[27]</a>

A simple modification of the Raz–McKenzie lifting theorem gives a lower bound of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta \cdot D(g)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta \cdot D(g)}</annotation>

</semantics>

</math><img src="./bd9c6d4103a753accb6d7b47656bd75b84e5e80b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.465ex; height:2.843ex;" alt="{\displaystyle \Delta \cdot D(g)}" loading="lazy"> on the logarithm of the size of a protocol tree for computing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\circ g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\circ g}</annotation>

</semantics>

</math><img src="./b2f61ca7838709fbae07dce9c0d513770f10cfae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.589ex; height:2.509ex;" alt="{\displaystyle f\circ g}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta }</annotation>

</semantics>

</math><img src="./32769037c408874e1890f77554c65f39c523ebe2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.936ex; height:2.176ex;" alt="{\displaystyle \Delta }" loading="lazy"> is the depth of the <a href="Optimal_decision" title="Optimal decision">optimal decision</a> tree for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">. Garg, Göös, Kamath and Sokolov extended this to the <a href="Directed_acyclic_graph" title="Directed acyclic graph">DAG</a>-like setting,<a href="#cite_note-28">[28]</a> and used their result to obtain monotone <a href="Circuit_complexity" title="Circuit complexity">circuit</a> lower bounds. The same technique has also yielded applications to <a href="Proof_complexity" title="Proof complexity">proof complexity</a>.<a href="#cite_note-29">[29]</a>

A different type of lifting is exemplified by Sherstov's pattern matrix method,<a href="#cite_note-30">[30]</a> which gives a lower bound on the quantum communication complexity of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\circ g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\circ g}</annotation>

</semantics>

</math><img src="./b2f61ca7838709fbae07dce9c0d513770f10cfae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.589ex; height:2.509ex;" alt="{\displaystyle f\circ g}" loading="lazy">, where g is a modified indexing gadget, in terms of the approximate degree of f. The approximate degree of a Boolean function is the minimal degree of a polynomial which approximates the function on all Boolean points up to an additive error of 1/3.

In contrast to the Raz–McKenzie proof which uses the method of simulation, Sherstov's proof takes a dual witness to the approximate degree of f and gives a lower bound on the quantum query complexity of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\circ g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\circ g}</annotation>

</semantics>

</math><img src="./b2f61ca7838709fbae07dce9c0d513770f10cfae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.589ex; height:2.509ex;" alt="{\displaystyle f\circ g}" loading="lazy"> using the generalized discrepancy method. The dual witness for the approximate degree of f is a lower bound witness for the approximate degree obtained via <a href="Dual_linear_program" title="Dual linear program">LP duality</a>. This dual witness is massaged into other objects constituting data for the generalized discrepancy method.

Another example of this approach is the work of Pitassi and Robere,<a href="#cite_note-31">[31]</a> in which an algebraic gap is lifted to a lower bound on <a href="Alexander_Razborov" title="Alexander Razborov">Razborov</a>'s rank measure. The result is a strongly exponential lower bound on the monotone circuit complexity of an explicit function, obtained via the Karchmer–Wigderson characterization<a href="#cite_note-32">[32]</a> of monotone circuit size in terms of communication complexity.

<div class="mw-heading mw-heading2"><h2 id="Open_problems">Open problems</h2></div>

Considering a 0 or 1 input matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}}">

<msub>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}}</annotation>

</semantics>

</math><img src="./8ec0cc3d5f48abac95dcfd8060acefcf11884876.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:22.643ex; height:3.176ex;" alt="{\displaystyle M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}}" loading="lazy">, the minimum number of bits exchanged to compute <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> deterministically in the worst case, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D(f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(f)}</annotation>

</semantics>

</math><img src="./9d5afbbd0e5cc5450dff4f0de2006936c4bc3acc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle D(f)}" loading="lazy">, is known to be bounded from below by the logarithm of the <a href="Rank_(linear_algebra)" title="Rank (linear algebra)">rank</a> of the matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{f}}</annotation>

</semantics>

</math><img src="./be53b2e05e15a7c85c9be0f4ba32d7f3ef28b98b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.39ex; height:2.843ex;" alt="{\displaystyle M_{f}}" loading="lazy">.

The <a href="Log-rank_conjecture" title="Log-rank conjecture">log rank conjecture</a> proposes that the communication complexity, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D(f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(f)}</annotation>

</semantics>

</math><img src="./9d5afbbd0e5cc5450dff4f0de2006936c4bc3acc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle D(f)}" loading="lazy">, is bounded from above by a constant power of the logarithm of the rank of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{f}}</annotation>

</semantics>

</math><img src="./be53b2e05e15a7c85c9be0f4ba32d7f3ef28b98b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.39ex; height:2.843ex;" alt="{\displaystyle M_{f}}" loading="lazy">. Since D(f) is bounded from above and below by polynomials of log rank<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M_{f})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M_{f})}</annotation>

</semantics>

</math><img src="./110c228fd212698d9950cf6c3783394d86c71a2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.2ex; height:3.009ex;" alt="{\displaystyle (M_{f})}" loading="lazy">, we can say D(f) is polynomially related to log rank<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M_{f})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M_{f})}</annotation>

</semantics>

</math><img src="./110c228fd212698d9950cf6c3783394d86c71a2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.2ex; height:3.009ex;" alt="{\displaystyle (M_{f})}" loading="lazy">. Since the rank of a matrix is polynomial time computable in the size of the matrix, such an upper bound would allow the matrix's communication complexity to be approximated in polynomial time. Note, however, that the size of the matrix itself is exponential in the size of the input.

For a randomized protocol, the number of bits exchanged in the worst case, R(f), was conjectured to be polynomially related to the following formula:

</mrow>

</mrow>

</msubsup>

</mrow>

</msubsup>

<msup>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log \min({\textrm {rank}}(M'_{f}):M'_{f}\in \mathbb {R} ^{2^{n}\times 2^{n}},(M_{f}-M'_{f})_{\infty }\leq 1/3).}</annotation>

</semantics>

</math><img src="./a7aa3127135ec4b50e79706b3a5b0191cc872c5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:55.341ex; height:3.676ex;" alt="{\displaystyle \log \min({\textrm {rank}}(M'_{f}):M'_{f}\in \mathbb {R} ^{2^{n}\times 2^{n}},(M_{f}-M'_{f})_{\infty }\leq 1/3).}" loading="lazy"></dd></dl>

Such log rank conjectures are valuable because they reduce the question of a matrix's communication complexity to a question of linearly independent rows (columns) of the matrix. This particular version, called the Log-Approximate-Rank Conjecture, was recently refuted by Chattopadhyay, Mande and Sherif (2019)<a href="#cite_note-33">[33]</a> using a surprisingly simple counter-example. This reveals that the essence of the communication complexity problem, for example in the EQ case above, is figuring out where in the matrix the inputs are, in order to find out if they're equivalent.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Lower bounds in communication complexity can be used to prove lower bounds in <a href="Decision_tree_complexity" class="mw-redirect" title="Decision tree complexity">decision tree complexity</a>, <a href="VLSI_circuit" class="mw-redirect" title="VLSI circuit">VLSI circuits</a>, data structures, <a href="Streaming_algorithms" class="mw-redirect" title="Streaming algorithms">streaming algorithms</a>, <a href="Space%E2%80%93time_tradeoff" title="Space–time tradeoff">space–time tradeoffs</a> for Turing machines and more.<a href="#cite_note-:0-2">[2]</a>

Conitzer and Sandholm<a href="#cite_note-34">[34]</a> studied the communication complexity of some common <a href="Electoral_system" title="Electoral system">voting rules</a>, which are essential in political and non political organizations. <a href="Compilation_complexity" class="mw-redirect" title="Compilation complexity">Compilation complexity</a> is a closely related notion, which can be seen as a single-round communication complexity.

<ul><li><a href="Gap-Hamming_problem" title="Gap-Hamming problem">Gap-Hamming problem</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFYao1979" class="citation cs2">Yao, A. C. (1979), "Some Complexity Questions Related to Distributive Computing", Proc. Of 11th STOC, 14: 209–213</cite>

</li>

<li id="cite_note-:0-2">^ <a href="#cite_ref-:0_2-0">a</a> <a href="#cite_ref-:0_2-1">b</a> <cite id="CITEREFKushilevitzNisan1997" class="citation book cs1">Kushilevitz, Eyal; <a href="Noam_Nisan" title="Noam Nisan">Nisan, Noam</a> (1997). Communication Complexity. Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-56067-2</bdi>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFCleveVan_DamNielsenTapp1999" class="citation book cs1">Cleve, Richard; Van Dam, Wim; Nielsen, Michael; Tapp, Alain (1999). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/3-540-49208-9_4">"Quantum Entanglement and the Communication Complexity of the Inner Product Function"</a>. <a rel="nofollow" class="external text" href="https://digital.library.unt.edu/ark:/67531/metadc706249/">Quantum Computing and Quantum Communications</a>. Lecture Notes in Computer Science. Vol. 1509. pp. 61–74. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-49208-9_4">10.1007/3-540-49208-9_4</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-65514-5</bdi>. <a href="OSTI_(identifier)" class="mw-redirect" title="OSTI (identifier)">OSTI</a> <a rel="nofollow" class="external text" href="https://www.osti.gov/biblio/661703">661703</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFNavascuésGuryanovaHobanAcín2015" class="citation journal cs1">Navascués, Miguel; Guryanova, Yelena; Hoban, Matty J.; Acín, Antonio (2015). <a rel="nofollow" class="external text" href="https://doi.org/10.1038/ncomms7288">"Almost quantum correlations"</a>. Nature Communications. 6 6288. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1403.4621">1403.4621</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2015NatCo...6.6288N">2015NatCo...6.6288N</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fncomms7288">10.1038/ncomms7288</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/25697645">25697645</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> W. van Dam, Nonlocality & Communication Complexity,

Ph.d. thesis, University of Oxford (1999).

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFBrassardBuhrmanLindenMéthot2006" class="citation journal cs1">Brassard, Gilles; Buhrman, Harry; Linden, Noah; Méthot, André Allan; Tapp, Alain; Unger, Falk (27 June 2006). "Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial". Physical Review Letters. 96 (25) 250401. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0508042">quant-ph/0508042</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2006PhRvL..96y0401B">2006PhRvL..96y0401B</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPhysRevLett.96.250401">10.1103/PhysRevLett.96.250401</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/16907289">16907289</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFBrunnerSkrzypczyk2009" class="citation journal cs1">Brunner, Nicolas; Skrzypczyk, Paul (24 April 2009). "Nonlocality Distillation and Postquantum Theories with Trivial Communication Complexity". Physical Review Letters. 102 (16) 160403. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0901.4070">0901.4070</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2009PhRvL.102p0403B">2009PhRvL.102p0403B</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPhysRevLett.102.160403">10.1103/PhysRevLett.102.160403</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/19518687">19518687</a>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFBotteronBroadbentProulx2024" class="citation journal cs1">Botteron, Pierre; Broadbent, Anne; Proulx, Marc-Olivier (14 February 2024). "Extending the Known Region of Nonlocal Boxes that Collapse Communication Complexity". Physical Review Letters. 132 (7) 070201. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2302.00488">2302.00488</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2024PhRvL.132g0201B">2024PhRvL.132g0201B</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPhysRevLett.132.070201">10.1103/PhysRevLett.132.070201</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/38427887">38427887</a>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFYao1977" class="citation conference cs1"><a href="Andrew_Yao" title="Andrew Yao">Yao, Andrew Chi-Chih</a> (1977). "Probabilistic computations: Toward a unified measure of complexity". 18th Annual Symposium on Foundations of Computer Science (sfcs 1977). IEEE. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1977.24">10.1109/SFCS.1977.24</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0272-5428">0272-5428</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFRazborov1992" class="citation journal cs1"><a href="Alexander_Razborov" title="Alexander Razborov">Razborov, Alexander</a> (1992). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2892%2990260-M">"On the distributional complexity of disjointness"</a>. Theoretical Computer Science. 106 (2): 385–390. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2892%2990260-M">10.1016/0304-3975(92)90260-M</a>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFBar-YossefJayramKumarSivakumar2004" class="citation journal cs1">Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D. (2004). <a rel="nofollow" class="external text" href="https://people.seas.harvard.edu/~madhusudan/courses/Spring2016/papers/BJKS.pdf">"An information statistics approach to data stream and communication complexity"</a> (PDF). Journal of Computer and System Sciences. 68 (4): 702–732. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2003.11.006">10.1016/j.jcss.2003.11.006</a>. Retrieved 1 December 2023.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFBarakBravermanChenRao2013" class="citation journal cs1"><a href="Boaz_Barak" title="Boaz Barak">Barak, Boaz</a>; <a href="Mark_Braverman" title="Mark Braverman">Braverman, Mark</a>; Chen, Xi; Rao, Anup (2013). <a rel="nofollow" class="external text" href="https://www.boazbarak.org/Papers/directsum.pdf">"How to Compress Interactive Communication"</a> (PDF). SIAM Journal on Computing. 42 (3): 1327–1363. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F100811969">10.1137/100811969</a>.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFBravermanRao2014" class="citation journal cs1"><a href="Mark_Braverman" title="Mark Braverman">Braverman, Mark</a>; Rao, Anup (2014). "Information equals amortized communication". IEEE Transactions on Information Theory. 60 (10): 6058–6069. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1106.3595">1106.3595</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.2014.2347282">10.1109/TIT.2014.2347282</a>.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFBravermanGargPankratovWeinstein2013" class="citation conference cs1"><a href="Mark_Braverman" title="Mark Braverman">Braverman, Mark</a>; Garg, Ankit; Pankratov, Denis; Weinstein, Omri (June 2013). STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing. Palo Alto, CA: ACM. pp. 151–160. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2488608.2488628">10.1145/2488608.2488628</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-2029-0</bdi>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFBravermanMoitra2013" class="citation conference cs1"><a href="Mark_Braverman_(mathematician)" title="Mark Braverman (mathematician)">Braverman, Mark</a>; Moitra, Ankur (1 June 2013). <a rel="nofollow" class="external text" href="https://eccc.weizmann.ac.il/report/2012/131/">"An information complexity approach to extended formulations"</a>. STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing. Palo Alto, CA: ACM. pp. 161–170. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2488608.2488629">10.1145/2488608.2488629</a>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFWeinstein2015" class="citation journal cs1">Weinstein, Omri (June 2015). <a rel="nofollow" class="external text" href="https://eccc.weizmann.ac.il/report/2015/060/">"Information Complexity and the Quest for Interactive Compression"</a>. ACM SIGACT News. 46 (2): 41–64. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2789149.2789161">10.1145/2789149.2789161</a>. Retrieved 1 December 2023.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFYannakakis,_M.1991" class="citation journal cs1">Yannakakis, M. (1991). "Expressing combinatorial optimization problems by linear programs". J. Comput. Syst. Sci. 43 (3): 441–466. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2891%2990024-y">10.1016/0022-0000(91)90024-y</a>.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFLovett" class="citation cs2">Lovett, Shachar, <a rel="nofollow" class="external text" href="https://cseweb.ucsd.edu/classes/wi19/cse291-b/4-unbounded.pdf">CSE 291: Communication Complexity, Winter 2019 Unbounded-error protocols</a> (PDF), retrieved June 9, 2019</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFGöösPitassiWatson2018" class="citation journal cs1">Göös, Mika; Pitassi, Toniann; Watson, Thomas (2018-06-01). <a rel="nofollow" class="external text" href="https://drops.dagstuhl.de/opus/volltexte/2016/6199/">"The Landscape of Communication Complexity Classes"</a>. Computational Complexity. 27 (2): 245–304. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00037-018-0166-6">10.1007/s00037-018-0166-6</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1420-8954">1420-8954</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:4333231">4333231</a>.</cite>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFSherstov2008" class="citation book cs1">Sherstov, Alexander A. (October 2008). "The Unbounded-Error Communication Complexity of Symmetric Functions". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. pp. 384–393. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ffocs.2008.20">10.1109/focs.2008.20</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7695-3436-7</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9072527">9072527</a>.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFForster,_Jürgen2002" class="citation journal cs1">Forster, Jürgen (2002). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2802%2900019-3">"A linear lower bound on the unbounded error probabilistic communication complexity"</a>. Journal of Computer and System Sciences. 65 (4): 612–625. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2802%2900019-3">10.1016/S0022-0000(02)00019-3</a>.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFAlonFranklRodl1985" class="citation book cs1">Alon, N.; Frankl, P.; Rodl, V. (October 1985). "Geometrical realization of set systems and probabilistic communication complexity". 26th Annual Symposium on Foundations of Computer Science (SFCS 1985). Portland, OR, USA: IEEE. pp. 277–280. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.300.9711">10.1.1.300.9711</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1985.30">10.1109/SFCS.1985.30</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780818606441</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8416636">8416636</a>.</cite>

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <cite id="CITEREFRazMcKenzie1999" class="citation journal cs1"><a href="Ran_Raz" title="Ran Raz">Raz, Ran</a>; McKenzie, Pierre (1999). "Separation of the Monotone NC Hierarchy". Combinatorica. 19 (3): 403–435. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs004930050062">10.1007/s004930050062</a>.</cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFGöösPitassiWatson2018" class="citation journal cs1">Göös, Mika; <a href="Toniann_Pitassi" title="Toniann Pitassi">Pitassi, Toniann</a>; Watson, Thomas (2018). <a rel="nofollow" class="external text" href="https://eccc.weizmann.ac.il/report/2015/050/">"Deterministic communication vs. partition number"</a>. SIAM Journal on Computing. 74 (6): 2435–2450. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F16M1059369">10.1137/16M1059369</a>.</cite>

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFChattopadhyayKouckýLoffMukhopadhyay2019" class="citation journal cs1">Chattopadhyay, Arkadev; Koucký, Michal; Loff, Bruno; Mukhopadhyay, Sagnik (2019). <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00037-019-00190-7">"Simulation theorems via pseudo-random properties"</a>. Computational Complexity. 28 (4): 617–659. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1704.06807">1704.06807</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00037-019-00190-7">10.1007/s00037-019-00190-7</a>.</cite>

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFLovettMekaMertzPitassi200" class="citation conference cs1">Lovett, Shachar; Meka, Raghu; Mertz, Ian; <a href="Toniann_Pitassi" title="Toniann Pitassi">Pitassi, Toniann</a>; Zhang, Jiapeng (200). <a rel="nofollow" class="external text" href="https://www.cs.toronto.edu/~mertz/papers/lmmpz20.lifting_with_sunflowers.pdf">"Lifting with Sunflowers"</a> (PDF). 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Vol. 215. Leibniz International Proceedings in Informatics (LIPIcs). pp. 104:1–104:24. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4230%2FLIPIcs.ITCS.2022.104">10.4230/LIPIcs.ITCS.2022.104</a>.</cite>

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> <cite id="CITEREFGöösPitassiWatson2017" class="citation conference cs1">Göös, Mika; <a href="Toniann_Pitassi" title="Toniann Pitassi">Pitassi, Toniann</a>; Watson, Thomas (2017). "Query-to-Communication Lifting for BPP". 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Berkeley, CA: IEEE. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1703.07666">1703.07666</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FFOCS.2017.21">10.1109/FOCS.2017.21</a>.</cite>

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFGargGöösKamathSokolov2020" class="citation journal cs1">Garg, Ankit; Göös, Mika; Kamath, Pritish; Sokolov, Dmitry (2020). <a rel="nofollow" class="external text" href="https://theoryofcomputing.org/articles/v016a013/">"Monotone Circuit Lower Bounds from Resolution"</a>. Theory of Computing. 16: 13:1–13:30. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4086%2Ftoc.2020.v016a013">10.4086/toc.2020.v016a013</a>.</cite>

</li>

<li id="cite_note-29"><a href="#cite_ref-29">^</a> <cite id="CITEREFde_RezendeMeirNordströmPitassi2020" class="citation conference cs1">de Rezende, Susanna; Meir, Or; Nordström, Jakob; <a href="Toniann_Pitassi" title="Toniann Pitassi">Pitassi, Toniann</a>; Robere, Robere; Vinyals, Marc (2020). "Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity". 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Virtual conference: IEEE. pp. 24–30. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2001.02144">2001.02144</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FFOCS46700.2020.00011">10.1109/FOCS46700.2020.00011</a>.</cite>

</li>

<li id="cite_note-30"><a href="#cite_ref-30">^</a> <cite id="CITEREFSherstov2011" class="citation journal cs1">Sherstov, Alexander (2011). "The pattern matrix method". SIAM Journal on Computing. 40 (6): 1969–2000. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0906.4291">0906.4291</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F080733644">10.1137/080733644</a>.</cite>

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> <cite id="CITEREFPitassiRobere2017" class="citation conference cs1"><a href="Toniann_Pitassi" title="Toniann Pitassi">Pitassi, Toniann</a>; Robere, Robert (2017). <a rel="nofollow" class="external text" href="https://www.cs.utoronto.ca/~toni/Papers/rp-stoc17.pdf">"Strongly Exponential Lower Bounds for Monotone Computation"</a> (PDF). STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Montreal: ACM. pp. 1246–1255. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3055399.3055478">10.1145/3055399.3055478</a>.</cite>

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> <cite id="CITEREFKarchmerWigderson1990" class="citation journal cs1">Karchmer, Mauricio; <a href="Avi_Wigderson" title="Avi Wigderson">Wigderson, Avi</a> (1990). <a rel="nofollow" class="external text" href="https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/KW90/KW90.pdf">"Monotone circuits for connectivity require super-logarithmic depth"</a> (PDF). SIAM Journal on Discrete Mathematics. 3 (2): 255–265. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0403021">10.1137/0403021</a>.</cite>

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> Chattopadhyay, Arkadev; Mande, Nikhil S.; Sherif, Suhail (2019). "The Log-Approximate-Rank Conjecture is False". 2019, Proceeding of the 51st Annual ACM Symposium on Theory of Computing: 42-53.<a rel="nofollow" class="external free" href="https://doi.org/10.1145/3313276.3316353">https://doi.org/10.1145/3313276.3316353</a>

</li>

<li id="cite_note-34"><a href="#cite_ref-34">^</a> <cite id="CITEREFConitzerSandholm2005" class="citation book cs1">Conitzer, Vincent; Sandholm, Tuomas (2005-06-05). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/1064009.1064018">"Communication complexity of common voting rules"</a>. <a rel="nofollow" class="external text" href="https://figshare.com/articles/journal_contribution/6604214">Proceedings of the 6th ACM conference on Electronic commerce</a>. EC '05. New York, NY, USA: Association for Computing Machinery. pp. 78–87. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1064009.1064018">10.1145/1064009.1064018</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-59593-049-1</bdi>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFRaoYehudayoff2020" class="citation book cs1">Rao, Anup; Yehudayoff, Amir (2020). Communication complexity and applications. Cambridge: Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781108671644</bdi>.</cite></li>

<li><cite id="CITEREFKushilevitzNisan2006" class="citation book cs1">Kushilevitz, Eyal; <a href="Noam_Nisan" title="Noam Nisan">Nisan, Noam</a> (2006). Communication complexity. Cambridge: Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-02983-4</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/70764786">70764786</a>.</cite></li>

<li>Brassard, G. Quantum communication complexity: a survey. <a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0101005">https://arxiv.org/abs/quant-ph/0101005</a></li>

<li>Dietzfelbinger, M., J. Hromkovic, J., and G. Schnitger, "<a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/pii/S030439759600062X/pdf?md5=673842d5f5b8a83d07e2c183ffa357a1&pid=1-s2.0-S030439759600062X-main.pdf&_valck=1">A comparison of two lower-bound methods for communication complexity</a>", Theoret. Comput. Sci. 168, 1996. 39-51.</li>

<li><a href="Ran_Raz" title="Ran Raz">Raz, Ran</a>. "Circuit and Communication Complexity." In Computational Complexity Theory. Steven Rudich and Avi Wigderson, eds. American Mathematical Society Institute for Advanced Study, 2004. 129-137.</li>

<li>A. C. Yao, "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC, pp. 209–213, 1979. 14</li>

<li>I. Newman, <a rel="nofollow" class="external text" href="http://u.cs.biu.ac.il/~zarosih/70/files/private_vs__common_random_bits_in_commun_493418.pdf">Private vs. Common Random Bits in Communication Complexity</a>, Information Processing Letters 39, 1991, pp. 67–71.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-29" href="https://en.wikipedia.org/wiki/?title=Communication_complexity&oldid=1303229251">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>